package com.example.algorithm.greedy;

/**
 * @author : zhy
 * @since : 2022/8/26
 * 买卖股票的最佳时机 II
 */
public class BuySharesTwo {


    /**
     * 贪心算法
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int len=prices.length;
        if(len==2)
        {
            int kk=prices[1]-prices[0];
            return kk>0?kk:0;
        }
        int sum=0;
        for(int i=1;i<len;i++)
        {
            sum+=Math.max(prices[i]-prices[i-1],0);
        }
        return sum;
    }


    /**
     * 动态规划
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices){
        int len=prices.length;
        //[天数][是否持有]
        int[][]dp=new int[len][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<len;i++)
        {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        //没有持有股票，到手的钱是最多的
        return dp[len-1][0];
    }

    public static void main(String[] args) {
        BuySharesTwo sharesTwo = new BuySharesTwo();
        int[] prices={7,1,5,3,6,4};
        int profit = sharesTwo.maxProfit(prices);
        System.out.println(profit);

        System.out.println("---------------------------");

        int profit1 = sharesTwo.maxProfit1(prices);
        System.out.println(profit1);
    }
}
